I - Coins
確率DPの問題。確率DPってなんや…？
問題意訳
それぞれのコインの表を向く確率が与えられます。
全てを同時に投げた時に表の数が裏の数より大きくなる確率を求めなさい。
コインの枚数 1 <= N <= 3000
考察
EDPCだし、一旦いつもの「i番目まで考えた時、表の数が裏の数より大きくなる確率」みたいなDPを考えてみます。
int dp[i] //i番目までのコインを投げた時、表の数の方が多い確率
でも実は、このままでは上手くいきません。俗に言う「状態を増やす作業」をしなければなりません。
何故状態を増やす必要が？
例えば次のような2つのパターンを考えてみます。
table:全てが裏になる
コイン 1 2 3 4 5 6 7 8
表を向く確率 0% 0% 0% 0% 0% 0% 0% 0%
このときdp[8]、「8枚目まで投げた時、表の方が多い確率」は0%になります。
table:やがて半々になる
コイン 1 2 3 4 5 6 7 8
表を向く確率 100% 100% 100% 100% 0% 0% 0% 0%
このときdp[8]、「8枚目まで投げた時、表の方が多い確率」は0%になります(ドローなので)。
ここで「必ず表が出るコイン」を末尾に追加することにします。すると
table:全てが裏になる + 必ず表
コイン 1 2 3 4 5 6 7 8 9 9
表を向く確率 0% 0% 0% 0% 0% 0% 0% 0% 0% 100%
table:やがて半々になる + 必ず表
コイン 1 2 3 4 5 6 7 8 9
表を向く確率 100% 100% 100% 100% 0% 0% 0% 0% 100%
このようになります。dp[9]の値を計算すると、上の場合は0%、下の場合だと100%になってしまうことが分かります。
つまり、同じdp[8] == 0でも、dp[9]が1や0になってしまう
本来は区別するべきだった「何枚表向いてんの？」みたいな情報を一緒くたにまとめてしまっている
ということで、「状態を増やすか…！！」という気持ちになります
ちなみに
「コインの枚数 N <= 3000 だから多分、1次元じゃないんだろうな…」みたいなことを考えることも可能です（え）
状態を増やす
これまでの基本系に、「j枚以上が表を向く」みたいな情報を付けていくことにします。
dp[i][j] // i番目までを投げた時に、j枚以上が表を向く確率
遷移をしてからdp[最後のコイン][コインの合計枚数/2+1]の結果を取り出せば良いわけです。つまり
「最後のコインまでを投げた時に、コインの合計枚数の半分よりも大きい数の表が出る確率」みたいな感じです。